package leetcode;

//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class problems_042 {

    public static void main(String[] arge){
        new Solution().trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1});
    }
    static class Solution {
        public int trap(int[] height) {
            int sum = 0;
            Stack<Integer> stack = new Stack<>();
            int current = 0;
            while (current < height.length) {
                //如果栈不空并且当前指向的高度大于栈顶高度就一直循环
                while (!stack.empty() && height[current] > height[stack.peek()]) {
                    int h = height[stack.peek()]; //取出要出栈的元素
                    stack.pop(); //出栈
                    if (stack.empty()) { // 栈空就出去
                        break;
                    }
                    int distance = current - stack.peek() - 1; //两堵墙之前的距离。
                    System.out.println("开始:" + stack.peek() + "，结束:" + current + "，长度：" + distance);
                    int min = Math.min(height[stack.peek()], height[current]);
                    sum = sum + distance * (min - h);
                }
                stack.push(current); //当前指向的墙入栈
                current++; //指针后移
            }
            return sum;
        }


//        public int trap(int[] height) {
//            int sum = 0;
//            int max = getMax(height);//找到最大的高度，以便遍历。
//            System.out.println("最高高度:" + max);
//            for (int i = 1; i <= max; i++) {
//                System.out.println("第:"+i+"行");
//                boolean isStart = false; //标记是否开始更新 temp
//                int temp_sum = 0;
//                for (int j = 0; j < height.length; j++) {
//                    System.out.print("--第:"+j+"列(isStart:"+isStart+")");
//                    if (isStart && height[j] < i) {
//                        temp_sum++;
//                    }
//                    if (height[j] >= i) {
//                        sum = sum + temp_sum;
//                        temp_sum = 0;
//                        isStart = true;
//                    }
//                }
//            }
//            return sum;
//        }
//        private int getMax(int[] height) {
//            int max = 0;
//            for (int i = 0; i < height.length; i++) {
//                if (height[i] > max) {
//                    max = height[i];
//                }
//            }
//            return max;
//        }
    }
}
